import java.util.Scanner;

public class ShortestPalindrome {
    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        int n = s.length();
        int i = 0;
        for (int j = n - 1; j >= 0; j--) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
            }
        }

        if (i == n) {
            return s;
        }

        String suffix = s.substring(i);
        String reverseSuffix = new StringBuilder(suffix).reverse().toString();
        String remaining = s.substring(0, i);

        return reverseSuffix + shortestPalindrome(remaining) + suffix;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入一个字符串: ");
        String input = scanner.nextLine();

        ShortestPalindrome sp = new ShortestPalindrome();
        String result = sp.shortestPalindrome(input);
        System.out.println("最短的回文串是: " + result);

        scanner.close();
    }
}
